While Insertion Sort offered an efficient $O(n)$ performance on nearly sorted inputs, its average and worst-case performance reveals a fundamental limitation shared by all simple sorts: the $O(n^2)$ time complexity barrier.
- This limitation stems from the Comparison Model used by Bubble, Selection, and Insertion Sorts, which relies on local, adjacent operations.
- To move an element far from its final destination (e.g., moving the smallest element from the end to the front), it costs $O(n)$ individual comparisons and shifts.
- Since this costly $O(n)$ process might have to be repeated for up to $n$ elements, the total complexity becomes $n \times O(n) = O(n^2)$.
- To break this barrier and achieve $O(n \log n)$ complexity, an algorithm must facilitate non-local movement of data.
- This requires a new strategy: Divide and Conquer, which introduces the crucial $\log n$ factor by recursively breaking the problem into smaller, manageable subproblems.
| Algorithm | Worst Case Complexity | Stability | In-Place |
|---|---|---|---|
| Bubble Sort | $O(n^2)$ | Yes | Yes |
| Selection Sort | $O(n^2)$ | No | Yes |
| Insertion Sort | $O(n^2)$ | Yes | Yes |